/**
 * 项目名称: topsort.cpp
 * 项目路径: study/DataStructure/数据结构/图/应用/拓扑排序
 * 编辑时间: 2024年08月12日15时55分26秒
 * 用   户: 轻尘
 */

#include <bits/stdc++.h>

using namespace std;
const int MaxVnum=100;//顶点数最大值

typedef int VexType;//顶点的数据类型为字符型
typedef struct AdjNode{ //定义邻接点类型
    int v; //邻接点下标
    struct AdjNode *next; //指向下一个邻接点
};

typedef struct VexNode{ //定义顶点类型
    VexType data; // VexType为顶点的数据类型，根据需要定义
    AdjNode *first; //指向第一个邻接点
}VexNode;

typedef struct{//定义邻接表类型
    VexNode  Vex[MaxVnum];
    int vexnum,edgenum; //顶点数，边数
}Graph;

int indegree[MaxVnum];

bool TopSort(Graph G){
    InitStack(S);//初始化栈,存储入度为0的结点
    for(int i=0;i<G.vexnum;i++)
        if(indegree[i] == 0)
            Push(S,i);//将所有入度为0的顶点进栈
     int count = 0;//计数,记录当前已经输出的顶点数
    while (!IsEmpty(S)){//栈不空,则存在入度为0的顶点
        int i =1
        Pop(S,i);//栈顶元素出栈
        print[count++]=i;//输出顶点i
        for(auto p=G.Vex[i].first;p;p=p->next){
            v=p->v;//将所有i指向的顶点的入度减1,并且将入度减为0的顶点压入栈s
            if(!(--indegree[i]))Push(S,v);//入度为0,则入栈
        }
    }

    if(count<G.vexnum)return false;//排序失败,有向图中有回路
    else return true;//拓扑排序成功
}

